Corelab Seminar
2019-2020
Ioannis Kokkinis
An Introduction to Dynamic Complexity
Abstract.
The goal of dynamic complexity is to determine the minimum resources
needed for maintaining the answer to a problem (query) when the input
(database) changes dynamically. An important dynamic complexity class is
the class DynFO which contains all queries that can be maintained using
first order formulas after single tuple insertions and deletions
into/from the
database. The class DynFO was introduced in 1997 by Patnaik and Immerman
as a small parallel descriptive complexity class that would help us
classify some dynamic database problems. Although the updates to
the problems belonging in DynFO are only possible in first-order logic,
DynFO has proven to be quite powerful: it even contains the reachability
query, which is a natural NL-complete problem. However several natural
questions for this class remain open, such as an exact comparison of
DynFO with classical (static) complexity classes and finding natural
complete problems for DynFO.
In this talk I will give an introduction to the fundamentals of Dynamic
Complexity and also a slight overview on some recent joint work with the
members of the group LOGIDAC in TU Dortmund: namely combining dynamic
complexity with parametrised complexity
and also studying the dynamic complexity of Acyclic Conjunctive Queries.